public class t45 {
    //45. 跳跃游戏 II 中等
    public static void main(String[] args) {
        int arr[] = {2,3,1,1,4};
        System.out.println(jump(arr));
    }
    //dp[i] = (dp[j]+1,dp[i])min : if arr[j] >= i-j
    public static int jump(int[] nums) {
        int len = nums.length;
        int dp[] = new int [len];
        dp[0] = 0;
        for(int i = 1;i<len;i++){
            dp[i] = Integer.MAX_VALUE;
            for(int j = 0;j<i;j++){
                if(nums[j]>=i-j&&dp[j]!=Integer.MAX_VALUE){
                    dp[i] = Math.min(dp[i],dp[j]+1);
                    break;
                }
            }
        }
        return dp[len-1];
    }
}
